[Coding022] Sort - 选择排序

简单选择排序

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：选择排序

选择排序（Selection sort）是一种简单直观的排序算法。

它的工作原理如下：

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；

2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。

• 选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对$n$$n$个元素的表进行排序总共进行至多$(n-1)$$(n-1)$次交换。

• 在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

——维基百科

选排思想

※ 典型过程手绘过程分析

Java语言代码实现

xxxxxxxxxx
77
1
import java.util.Scanner;
2

3
// 这是一个类，名叫Solution
4
public class Solution {
5
    /**
6
     * 简单选择排序(Selection Sort)
7
     */
8
    public static void main(String[] args) {
9
        // TODO Auto-generated method stub
10
        System.out.println("hello, my t!");
11

12
        Scanner input = new Scanner(System.in);
13

14
        int n = input.nextInt();
15

16
        int[] arr = new int[n];
17
        for (int i = 0; i < n; i++) 
18
        {
19
            arr[i] = input.nextInt();
20
        }
21

22
        for (int e : arr) {
23
            System.out.print(e + " ");
24
        }
25
        System.out.println("\n--------------");
26

27
        Solution sol = new Solution();
28
        sol.Selection_Sort(arr, arr.length);
29

30
        for (int e : arr) 
31
        {
32
            System.out.print(e + " ");
33
        }
34
        return;
35
    }
36

37
    public void Selection_Sort(int[] arr, int n) 
38
    {
39
        for (int i = 0; i < n - 1; i++) 
40
        {
41
            // 依次从前向后取一个数
42
            int idx = i;
43
            int val = arr[i];
44

45
            // 对比当前数后面所有的数，找到最小的那个数，记下val和idx
46
            for (int j = i + 1; j < n; j++) 
47
            {
48
                if (arr[j] < val) 
49
                {
50
                    idx = j;
51
                    val = arr[j];
52
                }
53
            }
54
            arr[idx] = arr[i]; // 把arr[i]位置腾出来（安置好arr[i]位置原来的值）
55
            arr[i] = val; // 赋值该有的值
56
        }
57
    }
58

59
}
60

61
/*
62
测试样例: 
63
5 
64
5 4 7 9 6
65

66
9 
67
65 70 75 80 85 60 55 50 45
68

69
10 
70
10 20 30 40 50 60 70 80 90 100
71

72
20 
73
12 54 63 54 87 52 49 32 65 48 90 27 30 65 3 9 6 14 18 0
74

75
10 
76
46 32 13 24 10 91 67 88 79 55
77
*/

运行结果

复杂度

复杂度分析

• （对于数组而言的选择排序）需要比较的次数（Number of comparisons）

  Does not depend on the initial order of the elements

  $$\begin{array}{c}C=\sum _{i=0}^{n-2}\sum _{j=i+1}^{n-1}1=\sum _{i=0}^{n-2}(n-1-i)=\sum _{i=1}^{n-1}(n-i)=\sum _{i=1}^{n-1}n-\sum _{i=1}^{n-1}i\\ =n(n-1)-\frac{n(n-1)}{2}=\frac{n(n-1)}{2}=O(n^2)\end{array}$$

• （对于数组而言的选择排序）需要移动的次数（Number of movements）

  边界情况	情况	复杂度
  MIN	(already in order)	$O(n)$$O(n)$
  MAX	(in reverse order)	$(D_i{)}_{max}=O(n^2)$$(D_i)_{max}=O(n^2)$